/*
 * mergeSort.hpp
 *
 *  Created on: Sep 12, 2011
 *      Author: dgdiniz
 */

#ifndef MERGESORT_HPP_
#define MERGESORT_HPP_

template<typename T>
void mergeSort(T list[], const unsigned length)
{
	unsigned mid;

	if (length <= 1) return; //There is nothing to sort here.

	mid = length/2;

	mergeSort(list, mid);
	mergeSort(list + mid, length - mid);

	T *buffer = new T[length]; //creating a temp list
	unsigned left=0, right=mid, i=0;

	while (left<mid && right<length)
	{
		if (list[left] <= list[right]) buffer[i++] = list[left++];
		else buffer[i++] = list[right++];
	}

	while (left<mid) buffer[i++] = list[left++];
	while (right<length) buffer[i++] = list[right++];

	for (i=0; i<length; i++) list[i] = buffer[i];

	delete[] buffer;
}


template<typename T>
void mergeSortDec(T list[], const unsigned length)
{
	unsigned mid;

	if (length <= 1) return; //There is nothing to sort here.

	mid = length/2;

	mergeSortDec(list, mid);
	mergeSortDec(list + mid, length - mid);

	T *buffer = new T[length]; //creating a temp list
	unsigned left=0, right=mid, i=0;

	while (left<mid && right<length)
	{
		if (list[left] >= list[right]) buffer[i++] = list[left++];
		else buffer[i++] = list[right++];
	}

	while (left<mid) buffer[i++] = list[left++];
	while (right<length) buffer[i++] = list[right++];

	for (i=0; i<length; i++) list[i] = buffer[i];

	delete[] buffer;
}

#endif /* MERGESORT_HPP_ */
